from typing import List

"""
循环回溯每一个变量，如果被访问过了，或者为0 跳过，else 进入回溯下一层
"""


class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m = len(grid)
        if not m:
            return 0
        n = len(grid[0])
        max_area = 0
        d = ((-1, 0), (1, 0), (0, -1), (0, 1))

        def in_area(i: int, j: int):
            """是否在区域内"""
            return i >= 0 and j >= 0 and i < m and j < n

        def helper(x: int, y: int):
            """x,y 表示坐标
            """
            
            if not in_area(x, y) or grid[x][y] != 1:
                return 0
            print(x, y)
            grid[x][y] = 0
            res = 1
            for c in d:
                new_x = x + c[0]
                new_y = y + c[1]

                res += helper(new_x, new_y)
            return res

        for i in range(m):
            for j in range(n):
                max_area = max(helper(i, j), max_area)
        return max_area


if __name__ == "__main__":
    s = [
        [0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
        [0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0],
        [0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0],
    ] # 6


    print(Solution().maxAreaOfIsland(s))  # 6
